Gates

Memory limit: 96 MB

After many years of working as a software developer you have decided to try something entirely different, and started looking at random job offers. The one that really caught your eye was a job in fish farming (a form of aquaculture). 'Cool!', you thought, and besides, fish are nice creatures. So you applied, got accepted, and today is your first day at work.

Your boss has already assigned you a task. You have to isolate one water reservoir from another. After looking at some schemes you've been given, here's what you've figured out.

The two water reservoirs are connected by several channels. Each channel has two gates. The channel is open when both gates are open, and is closed otherwise. The gates are controlled using switches. The same switch may operate several gates, but each gate is operated by exactly one switch. It is possible that both gates on a channel are controlled by the same switch and that a switch controls no gates.

Example with three channels and two switches.

The switch may operate the gate in one of two ways:

• the gate is open when the switch is on, and is closed when the switch is off,
• the gate is closed when the switch is on, and is open when the switch is off.

After playing a bit with the switches you suddenly realize that your programming experience will come in very handy. Write a program that, given the configuration of gates and switches, determines whether it is possible to close all channels, and if it is, then finds a state of every switch in one such valid configuration.

Input

The first line of the standard input contains two integers and , the number of channels and switches respectively. Switches are numbered from to . Additionally, in test cases worth at least points, will not exceed and will not exceed .

The following lines describe channels, each channel is described by a separate line containing four integers: , , , . Numbers and represent switches () that operate gates of this channel. Numbers and can be either or and correspond to the described operation modes: means that the gate is closed if and only if the switch is off and means that the gate is closed if and only if the switch is on.

Output

If it is possible to close all the channels, the standard output should contain lines. Line should contain , if switch should be off, and if switch should be on. If there are many possible solutions, your program may output any of them.

If it is impossible to close all channels, your program should output one line, containing a single word IMPOSSIBLE.

Example

For the input data:

3 2
1 0 2 1
1 0 2 0
1 1 2 1

the correct result is:

0
1

and for the input data:

2 1
1 0 1 0
1 1 1 1

the correct result is:

IMPOSSIBLE

The first example corresponds to the picture from the task description.

Task author: Linas Petrauskas.